/**
 * 堆排序
 *
 * @Author: wanqian
 * @Date: 2021/2/8 9:40
 */
public class HeapSort {
    public static int[] arr = {4, 6, 8, 5, 9};

    public static int count;

    public static void main(String[] args) {
        int[] arr = new int[1000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 1000);
        }
//        System.out.println("排序前" + Arrays.toString(arr));
        long start = System.currentTimeMillis();
        heapSort(arr);
        long end = System.currentTimeMillis();
        long consume = (end - start);
        System.out.println("耗时" + consume + "毫秒");
//        System.out.println(String.format("快速排序后： %s", Arrays.toString(arr)));

    }

    /**
     * 堆排序
     *
     * @param arr
     */
    public static void heapSort(int[] arr) {

        //1. 初始化排序。从最后一个非子节点开始向上进行排序，调整为大顶堆
        //2. 经过初始化排序后为大顶堆，即父节点一定大于子节点，但是子节点的大小关系并没有要求
        //3. 此时只能保证堆顶事最大值，无法保证子节点顺序
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        //取出当前堆顶节点与末尾进行交换，此时末尾为最大数
        //由于堆顶改变，此时重新排序(不包括最后一个数)，循环往复得出有序数组
        for (int j = arr.length - 1; j > 0; j--) {
            int temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }

    }


    /**
     * 从指定节点开始向下调整为大顶堆
     *
     * @param arr
     * @param index
     * @param length
     */
    public static void adjustHeap(int[] arr, int index, int length) {
//        System.out.println("第" + ++count + "次排序前: " + Arrays.toString(arr));
        //保存最初节点值
        int temp = arr[index];
        for (int i = index * 2 + 1; i < length; i = i * 2 + 1) {
            //比较子节点大小
            if (i + 1 < length && arr[i] < arr[i + 1]) {
                //若右节点更大，则将指针指向右节点
                i++;
            }
            //若较大的子节点大于父节点
            if (arr[i] > temp) {
                //将较大值赋给父节点
                arr[index] = arr[i];
                //注意！此处可以理解为将temp的值放在了子节点上，类似交换位置
                //因为交换了节点值，所以要继续判断子节点下的节点是否大于最初的temp
                index = i;
            } else {
                break;
            }
        }
        arr[index] = temp;
//        System.out.println("第" + count + "次排序后: " + Arrays.toString(arr));
    }
}
